#ifndef __MYHASH_HPP__
#define __MYHASH_HPP__

#include <iostream>
#include <vector>
#include <string>


// 简单仿函数实现，这里提供两个：1.数字仿函数  2.字符串仿函数
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

// 对于字符串仿函数我们做一个特化
template<>
struct HashFunc<std::string>
{
    // 使用bkdr-hash算法实现
    size_t operator()(const std::string& key)
    {
        // 使用一个素数31进行计算
        size_t seed = 31;
        size_t k = 0;
        for (auto a : key)  // hash(abcd) = (a * 31^3 + b * 31^2 + c * 31^1 + d * 31^0) % 4
        {
            k = k * seed + a;
        }
        return k;
    }
};


namespace close_hash
{
    // 闭散列实现哈希表

    // 利用枚举，列举出不同的类型
    enum State
    {
        EMPTY,  // 空
        EXIST, // 存在
        DELETE  // 删除
    };

    // 我们定义数据对象，因为不仅仅需要存储数据，我们还需要其的状态：1.空(默认为空) 2.存在 3.删除(需要和空区别开的原因就是线性探测需要到删除状态)
    template<class K, class V>
    struct HashElem  // 哈希元素
    {
        std::pair<K, V> kv;
        State state = State::EMPTY;  // 默认为空
    };

    // 模板类，我们需要应对不同类型的key-value结构，并且key不一定是size整数，我们需要能够将key转换为一个整数的能力
    // K和V均为类型，hash为对应的仿函数，能够提供解析后的结果
    // 闭散列实现，哈希冲突利用线性探测
    template<class K, class V, class hash=HashFunc<K>>
    class HashTable
    {
    private:
        std::vector<HashElem<K, V>> _data;  // 存放哈希元素的容器，利用STL中的数组
        // 当前容器长度可以由_data.size决定，但是需要存放我们实时的长度，用于计算负载因子，超过了0.7需要进行扩容
        size_t _size;  // 当前负载数
    public:
        // 构造函数，初始化容器长度、以及负载数位0
        HashTable(size_t len = 10)
        :_data(len), _size(0)
        {}
        ~HashTable()
        {}
        bool insert(const std::pair<K, V>& kv);
        bool erase(const K& key);
        HashElem<K, V>* find(const K& key);
        void dilatation();
        // 显示当前负载数：
        size_t size()
        {
            return _size;
        }
        // 当前容量
        size_t capacity()
        {
            return _data.size();
        }
        // 当前负载因子
        double loadfactor()
        {
            return size() * 1.0 / capacity();
        }
    };


    // close_hash实现

    // find查找函数
    // 成功返回HashElem指针，否则nullptr
    template<class K, class V, class hash>
    HashElem<K, V>* HashTable<K, V, hash>::find(const K& key)
    {
        // 根据k，利用hash仿函数找到其整数数值，除留余数法
        size_t len = _data.size();
        if (len == 0) return nullptr;  // 防止data数组为空出现除零错误
        size_t index = hash()(key) % len;

        // 开始线性探测，查找是否存在和key一致的数据元素
        while(_data[index].state != State::EMPTY)
        {
            if (_data[index].state == State::EXIST)
            {
                if (_data[index].kv.first == key) return &_data[index];
            }
            ++index;
            index %= len;  // 防止越界
        }
        return nullptr;  // 没有找到
    }

    // 扩容函数
    // 判断是否扩容函数
    // 如果负载因子（负载数/数组总长度）> 0.7扩容，或者数组长度为空
    template<class K, class V, class hash>
    void HashTable<K, V, hash>::dilatation()
    {
        size_t len = _data.size();
        if (len == 0 || _size*1.0 / len > 0.7)
        {
            // 扩容
            size_t newLen = len == 0 ? 10 : len * 2;
            HashTable<K, V, hash> _hashtable(newLen);  // 提前将空间定为不会发生冲突的状态，所以下面的子对象不会递归dilatation函数的状态
            for (auto& o : _data)
            {
                if (o.state == State::EXIST) _hashtable.insert(o.kv);  // 存在的进行映射即可
            }
            _data.swap(_hashtable._data);  // vector交换即可
        }
    }

    // 插入函数
    // 根据传入的key值，利用hash函数找到唯一的key值在vector进行一个插入
    // 插入元素 防止数据冗余，如果相同key插入拒绝
    template<class K, class V, class hash>
    bool HashTable<K, V, hash>::insert(const std::pair<K, V>& kv)
    {
        // 防止冗余，先进行查找
        if(nullptr != find(kv.first)) return false;  // 已经存在相同的值了
        //无重复值，先查看是否存在扩容，该扩容扩容，防止hash效率低下
        dilatation();
        // 此时映射一个唯一值进行插入
        size_t index = hash()(kv.first) % _data.size();
        while(_data[index].state == State::EXIST)
        {
            ++index;
            index %= _data.size();
        }
        // 此时要么state为空要么是删除的元素，插入即可
        _data[index].kv = kv;
        _data[index].state = State::EXIST;
        ++_size;  // 别忘了增加负载数

        return true;
    }

    // 删除函数
    // 根据传入的key值，对其进行一个删除
    template<class K, class V, class hash>
    inline bool HashTable<K, V, hash>::erase(const K& key)
    {
        // 首先找到此元素
        HashElem<K, V>* elem = find(key);
        if (elem == nullptr) return false;  // 不存在这样的值，无法删除
        // 否则存在，直接置为delete状态即可
        elem->state = State::DELETE;
        --_size;  // 别忘了负载数需要减少
        return true;
    }    
}

namespace open_hash
{
    // 开散列实现哈希，此时为哈希桶，负载因子无须考虑，满了扩充，每次扩充素数个即可。

    // 哈希桶节点
    template<class K, class V>
    struct HashBucketNode
    {
        std::pair<K, V> kv;
        HashBucketNode* next = nullptr;
    };

    // 哈希桶
    template<class K, class V, class hash=HashFunc<K>>
    class HashBucket
    {
        typedef HashBucketNode<K, V> Node;
    private:
        std::vector<Node*> _data;
        size_t _size;  // 实际数据个数
    public:
        // 构造函数
        HashBucket(size_t len = 11)
        :_size(0)
        {
            _data.resize(len, nullptr);
        }
        // 析构函数
        ~HashBucket()
        {
            // 因为Node节点均为new出来的，所以需要释放其空间
            size_t len = _data.size();
            for (size_t i = 0; i < len; ++i)
            {
                Node* cur = _data[i];
                while (cur)
                {
                    Node* next = cur->next;

                    delete cur;
                    cur = next;
                }
                _data[i] = nullptr;
            }
        }

        bool insert(const std::pair<K, V>& kv);
        bool erase(const K& key);
        Node* find(const K& key);
        // 当前桶的个数
        size_t BucketCount()
        {
            return _data.size();
        }
        // 当前有效数据个数
        size_t size()
        {
            return _size;
        }
    private:
		size_t __stl_next_prime(size_t n);
        void CheckCapacity();
    };

    //// open_hash 定义实现处

    // 每次返回一个素数 - 这样每次摸上一个素数 - 扩容就按这个标准来
    template<class K, class V, class hash>
    size_t HashBucket<K, V, hash>::__stl_next_prime(size_t n)
    {
        static const size_t __stl_num_primes = 28;
        static const size_t __stl_prime_list[__stl_num_primes] =
        {
            53, 97, 193, 389, 769,
            1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433,
            1572869, 3145739, 6291469, 12582917, 25165843,
            50331653, 100663319, 201326611, 402653189, 805306457,
            1610612741, 3221225473, 4294967291
        };

        for (size_t i = 0; i < __stl_num_primes; ++i)
        {
            if (__stl_prime_list[i] > n)
            {
                return __stl_prime_list[i];
            }
        }

        return -1;  // 扩容的量很大了
    }

    // 扩容函数
    template<class K, class V, class hash>
    void HashBucket<K, V, hash>::CheckCapacity()
    {
        if (_size == _data.size())
        {
            // 满了，或者为空
            size_t newbucketcount = _size == 0 ? 11 : __stl_next_prime(_size);
            std::vector<Node*> newdata;
            newdata.resize(newbucketcount, nullptr);

            // 每个桶上的每个节点进行重新映射
            // 不可复用insert，复用insert会导致临时对象释放掉指针空间，导致野指针引用哦
            for (size_t i = 0; i < _size; ++i)
            {
                Node* cur = _data[i];

                while (cur)
                {
                    Node* next = cur->next;

                    size_t index = hash()(cur->kv.first) % newbucketcount;
                    cur->next = newdata[index];
                    newdata[index] = cur;

                    cur = next;
                }
                _data[i] = nullptr;
            }
            _data.swap(newdata);
        }
    }

    template<class K, class V, class hash>
    typename HashBucket<K, V, hash>::Node* HashBucket<K, V, hash>::find(const K& key)  // 注意Node前面需要表明是一个类型，即typename，否则编译器识别不出来
    {
        if (_size == 0) return nullptr;
        size_t index = hash()(key) % _data.size();
        Node* cur = _data[index];

        while(cur)
        {
            if (cur->kv.first == key) return cur;
            cur = cur->next;
        }
        return nullptr;
    }

    template<class K, class V, class hash>
    bool HashBucket<K, V, hash>::insert(const std::pair<K, V>& kv)
    {
        if (nullptr != find(kv.first)) return false;  // 防止冗余
        CheckCapacity();  // 检查是否需要扩容

        size_t index = hash()(kv.first) % _data.size();
        Node* newnode = new Node;
        newnode->kv = kv;
        // 头插
        newnode->next = _data[index];
        _data[index] = newnode;

        ++_size;
        return true;
    }

    template<class K, class V, class hash>
    bool HashBucket<K, V, hash>::erase(const K& key)
    {
        if(nullptr == find(key)) return false;// 检查是否存在

        size_t index = hash()(key) % _data.size();
        Node* pre = nullptr;
        Node* cur = _data[index];

        while (cur)
        {
            if (cur->kv.first == key)
            {
                // 找到了，判断是什么删除
                if (nullptr == pre)
                {
                    // 头删
                    pre = cur->next;
                    _data[index] = pre;
                    delete cur;
                }
                else
                {
                    // 否则就是中间删
                    pre->next = cur->next;
                    delete cur;
                }
                return true;
            }
            pre = cur;
            cur = cur->next;
        }

        return false;
    }   

}
#endif